/**
 * 82. 删除排序链表中的重复元素 II
 * https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/
 */
public class Solutions_82 {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode cur = head;
        cur.next = new ListNode(2);
        cur = cur.next;
        cur.next = new ListNode(3);
        cur = cur.next;
        cur.next = new ListNode(3);
        cur = cur.next;
        cur.next = new ListNode(4);
        cur = cur.next;
        cur.next = new ListNode(4);
        cur = cur.next;
        cur.next = new ListNode(5);  // output: {1,2,5}

//        ListNode head = new ListNode(1);
//        ListNode cur = head;
//        cur.next = new ListNode(1);
//        cur = cur.next;
//        cur.next = new ListNode(1);
//        cur = cur.next;
//        cur.next = new ListNode(2);
//        cur = cur.next;
//        cur.next = new ListNode(3);  // output: {2,3}

        ListNode result = deleteDuplicates(head);
        System.out.println(result);
    }

    /**
     * 删除升序链表中的重复元素
     * @param head
     * @return
     */
    public static ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            // 结点为空或者下一结点为空时，一定不是重复的结点
            return head;
        }
        /**
         * 关键：判断当前结点与下一结点是否值相同
         */
        if (head.val == head.next.val) {
            // 值相同时，循环移动到 前一结点值 不同的结点上
            while (head != null && head.next != null && head.val == head.next.val) {
                head = head.next;
            }
            // 递归下一结点，返回的值，作为头结点
            // 以 {1,1,1,2,5} 为例：while 循环后，得到最后一个结点 1，因为 3 个 1 是重复的结点
            // 故而递归下一节点 2，并将返回的值，作为头结点，因为前面 3 个 1 是重复的结点
            head = deleteDuplicates(head.next);
        } else {
            // 不同时，遍历下一结点，并 将下一结点返回的值，作为 当前遍历结点的下一节点
            head.next = deleteDuplicates(head.next);
        }
        return head;
    }
}
